The two-dimensional Discrete Fourier Transform is defined as follows: ##EQU1## This transform is generally evaluated either by the classical row-column method (radix-2 method) or by the vector radix method.
Many applications of digital signal processing require the evaluation of discrete Fourier transforms (DFT's) of multidimensional sequences. The case of two-dimensional discrete Fourier transforms has been widely applied in the area of filtering, image enhancement, image coding, image compression and restoration, radar detection, computerized tomography, nuclear magnetic resonance (NMR) tomography and seismic analysis.
Since the apperance of the original Cooley-Tukey method in 1965, the standard methods of computing the two-dimensional discrete Fourier transform have been governed by the separability of two-dimensional DFT. Two-dimensional Fourier transform has been decomposed into two one-dimensional DFT by using the one-dimensional fast Fourier Transform (FFT) to execute the transform either in row-column-wise or in column-row-wise format.
Matrix transposition and high input/output bandwidth are two major problems associated with the use of a row-column (or column-row) method for the two-dimensional DFT. Therefore techniques to efficiently store the data in a secondary storage device such that it can avoid matrix transposition or minimize the traffic between the main memory and secondary memory, as done by the present invention, are very crucial in the execution of the FFT.
In prior art applications the matrix is stored on a mass storage device, e.g. a disk or a tape, where the smallest record that can be easily accessed is either an entire row or column. The way in which the data is stored facilitates data access for one-dimension but impedes data access of another dimension. The decomposition of each row (column) to transpose it into a column (row) severely degrades the performance of the implementation of a two-dimensional FFT either in conventional machines, especially virtual memory machines or Single Instruction Multiple Data (SIMD) machines. Even efficient matrix transposition algorithms pose serious bottlenecks for most super vector machines in performing vector gathering operations. In the prior art, the matrix transposition problem was eased by employing a staging memory proposed between the memory and the processor. The staging memory can reformat or corner-tune the array of data, making it compatible with the fast Fourier transform unit. See. FIG. 1.
For example, the naive or direct method for computing the one-dimensional DFT in Equation (1) required N.sup.2 multiplications. However the one-dimensional fast Fourier transform (1-D FFT) is a method to reduce the requirement to (N log N) multiplications. Methods for the 1-D FFT can be classified into full parallel, iterative parallel, cascade, and scalar structure. Computational tasks involving two-dimensional discrete Fourier transforms are computationally intensive and need a very high input-output bandwidth. SIMD machines have been proposed to map the row-column-wise decomposition (radix-2 method) of a two-dimensional fast Fourier transform (2DFFT). Array processors with radix-2 methods for 2DFFT using the corner-tuning mechanism have been proposed. Pipelined processors with vector radix-2.times.2 for 2DFFT have also been proposed. There is a need to have a highly efficient architecture for 2DFFT, especially in the environment of raster-scan or serial input/output devices.
Accordingly it is an object of the present invention to provide a method and apparatus for processing data to obtain a Fourier transform of data presented in a multi-dimensional format.
It is a further object of the present invention to provide a method and apparatus for processing data to obtain a Fourier transform of data presented in a two-dimensional matrix using the data from the matrix for the transformation without the necessity of transposing the matrix.
It is a further object of the present invention to provide a method and apparatus for processing data to obtain a Fourier transform of data presented in a two-dimensional matrix, and drive the arithmetic processors in a pipelined fashion.
It is a further object of the present invention to provide a method and apparatus for processing data to obtain a Fourier transform of data presented in a two-dimensional format using input and output devices that transmit data serially, or in raster scan manner.
These and other objects of the invention will become clear to those having the benefit of this disclosure.